package scuts.collections.immutable;
import scuts.core.extensions.Ints;
import scuts.core.types.Ordering;


class BinTrees {
  
  public static function make <T>(v:T, cmp:T->T->Ordering):BinTree<T> {
    return makeEmpty(cmp).insert(v);
  }
  
  public static function makeEmpty <T>(cmp:T->T->Ordering):BinTree<T> {
    return new Empty(cmp);
    
  }
  
}



interface BinTree<T> {
  public function isLeaf ():Bool;
  public function isEmpty ():Bool;
  public function insert (v:T):BinTree<T>;
  
  public function value ():T;
  
  public function remove (f:T->Bool):BinTree<T>;
  
  public function right ():BinTree<T>;
   
  
  public function left ():BinTree<T>;
  public function combine (t:BinTree<T>):BinTree<T>;
   
  public function size ():Int;
  
  public function minPathLength():Int;
  public function maxPathLength():Int;
  
  public function isBalanced():Bool;
}


class Empty<T> implements BinTree<T> {
  
  var cmp:T->T->Ordering;
  
  public function new (cmp:T->T->Ordering) {
    this.cmp = cmp;
  }
  
  public function isLeaf ():Bool {
    return true;
  }
  
  public function isEmpty ():Bool {
    return true;
  }
  
  public function value ():T {
    throw "Error";
    return null;
  }
  
  public function insert (v:T):BinTree<T> {
    return new Node(v, this, this, cmp, this);
  }
  public function remove (f:T->Bool):BinTree<T> {
    return this;
  }
  
  public function right ():BinTree<T> {
    return this;
  }
  
  public function left ():BinTree<T> {
    return this;
  }
  
  public function combine (t:BinTree<T>) {
    return t;
  }
  
  public function size ():Int {
     return 0;
  }
  
  public function minPathLength() return 0
  public function maxPathLength() return 0
  public function isBalanced() return true
}

// right > left <=
class Node<T> implements BinTree<T> {
  var leftTree:BinTree<T>;
  var rightTree:BinTree<T>;
  var val:T;
  var empty:Empty<T>;
  
  var cmp:T->T->Ordering;
  
  public function isEmpty ():Bool {
    return false;
  }
  
  public function new (value:T, left:BinTree<T>, right:BinTree<T>, cmp:T->T->Ordering, empty:Empty<T>) {
    this.leftTree = left;
    this.rightTree = right;
    this.cmp = cmp;
    this.val = value;
    this.empty = empty;
  }
  
  public function right ():BinTree<T> {
    return rightTree;
  }
  
  public function left ():BinTree<T> {
    return leftTree;
  }
  
  public function value ():T {
    
    return val;
  }
  
  public function size ():Int {
     return 1 + leftTree.size() + rightTree.size();
  }
  
  
  public function isLeaf ():Bool {
    return leftTree.isEmpty() && rightTree.isEmpty();
  }
  
  public function insert (v:T):BinTree<T> {
    return switch (cmp(val, v)) {
      case Ordering.LT:
        // insert right
        new Node(val, leftTree, rightTree.insert(v), cmp, empty);
      
      case Ordering.GT, Ordering.EQ:
      
        // insert left
        new Node(val, leftTree.insert(v), rightTree, cmp, empty);
    }
  }
  
  public function remove (f:T->Bool):BinTree<T> {
    return if (f(val)) {
      removeRoot().remove(f);
    } else {
      new Node(val, leftTree.remove(f), rightTree.remove(f), cmp, empty);
    }
  }
  
  public function removeRoot ():BinTree<T> {
    return if (leftTree.isEmpty()) {
      rightTree;
    } else if (rightTree.isEmpty()) {
      leftTree;
    } else {
      new Node(leftTree.value(), leftTree.left(), rightTree.combine(leftTree.right()), cmp, empty);
    }
  }
  
  public function combine (t:BinTree<T>) {
    return if (t.isEmpty()) {
      this;
    } else {
      // new head
      var c = cmp(val, t.value());
      
      switch (c) {
        case LT, EQ: 
          new Node(val, leftTree, t.combine(rightTree), cmp, empty);
        case GT:
          new Node(t.value(), t.left(), combine(t.right()), cmp, empty);
      }
    }
    
  }
  
  public function maxPathLength()
  {
    return 1 + Ints.max(leftTree.maxPathLength(), rightTree.maxPathLength());
  }

  public function minPathLength()
  {
    return 1 + Ints.min(leftTree.minPathLength(), rightTree.minPathLength());
  }
  
  public function isBalanced() {
    return
      maxPathLength() -
      minPathLength() <= 1;
  }
  
 
}